package com.leetcode.partition2;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/8/12 10:57
 */
public class LC139单词拆分 {

    public static boolean wordBreak(String s, List<String> wordDict) {
        return dynamicProgramming(s, wordDict);
//        Set<String> wordSet = new HashSet<>(wordDict);
//        return backtracking(s, 0, wordSet);

//        Set<Integer>[] memory = new Set[s.length()];     //memory[i]记录当前位置已经尝试过的wordDict中且尝试失败的元素
//        for (int i = 0; i < memory.length; i++) {
//            memory[i] = new HashSet<>();
//        }
//        //对wordDict按照字符串长度从小到大排序，探索时，如当前位置+wordDict中单词长度大于s的长度时，没必要继续探索了
//        wordDict.sort(Comparator.comparing(String::length));
//        return memoryBacktracking(s, 0, wordDict, memory);
    }

    public static void main(String[] args) {
        String s = "applepenapple";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("apple");
        wordDict.add("pen");
        System.out.println(wordBreak(s, wordDict));
    }

    private static boolean memoization(String str, int index, List<String> wordDict, Set<Integer>[] memory) {
        if (index >= str.length()) return true;
        for (int i = 0; i < wordDict.size(); i++) {                     //遍历字典的数据
            if ((index + wordDict.get(i).length()) > str.length()) return false;            //避免后续的切割越界，当前越界也就没必要继续执行
            String subStr = str.substring(index, index + wordDict.get(i).length());             //根据字典中的单词长度切割出子串
            if (memory[index].contains(i)) continue;

            if (!subStr.equals(wordDict.get(i))) continue;
            //当前切割出的第一个子串存在字典中，尝试继续切割后面的串
            if (memoization(str, index + wordDict.get(i).length(), wordDict, memory)) {
                return true;
            }
            memory[index].add(i);
        }
        return false;
    }

    private static boolean dynamicProgramming(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        //dp[i]代表s[0, i - 1]为止都能拆分后在字典中找到
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                String str = s.substring(j, i);
                //要求当前子串s[j, i - 1]能被查询到，且必须s[0, j - 1]也能被正确查询
                if (wordSet.contains(str) && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[s.length()];
    }

    private static boolean backtracking(final String s, int index, Set<String> wordSet) {
        if (index >= s.length()) return true;
        for (int i = index; i < s.length(); i++) {
            String word = s.substring(index, i + 1);
            if (wordSet.contains(word) && backtracking(s, i + 1, wordSet)) {
                return true;
            }
        }
        return false;
    }
}
